#pragma once
#include<climits>
#include<iostream>
#include<map>
#include<vector>
#include<iomanip>
#include<queue>
using namespace std;


namespace matrix{
    template<class v, class w, w max_v = INT_MAX, bool direction = false>
    class graph{
        public:
        // zdl:: 手动添加边
            graph(const v* a, size_t n)
            {
                _vectexs.reserve(n);
                for (int i = 0; i < _matrix.size(); i++)
                {
                    _vectexs.emplace_back(a[i]);
                    _indexMap[a[i]] = i;
                }
                // 现在开始初始化邻接矩阵
                _matrix.resize(n);
                for (int i = 0; i < _matrix.size(); i++)
                {
                    _matrix[i].resize(n, max_v);
                }
            }
            size_t getVertexIndex(const v& vec)
            {
                auto it = _indexMap.find(vec);
                if (it != _indexMap.end())
                {
					return it->second;
                }
                else
                {
                    throw invalid_argument("非法的参数：顶点不存在");
                    return -1;
                }
            }
            void addEdge(const v& src, const v& dst, const w& W)
            {
                size_t srcindex = getVertexIndex(src);
                size_t dstindex = getVertexIndex(dst);
                _matrix[srcindex][dstindex] = W;
                if (direction)
                {
                    _matrix[dstindex][srcindex] = W;
                }
            }
        // zdl:: 遍历bfs
        void bfs(const v& src)
        {
            size_t srcindex = getVertexIndex(src);
            queue<int> q;
            vector<bool> visted(_vectexs.size(), false);

            // 队列和标记数组
            q.emplace(srcindex);
            visted[srcindex] = 1;
            while (q.size())
            {
                auto t = q.front(); q.pop();
                visted[t] = true;
                cout << t  << ":" << _vectexs[t] << endl;
                // front 邻接的顶点放入队列
                for (size_t i = 0; i < _vectexs.size(); i++)
                {
                    if (_matrix[t][i] != max_v && !visted[i])
                    {
                        q.emplace(i);
                        visted[i] = true;
                    }
                }
            }

            cout << endl;
        }
        void print()
        {
            // 顶点
            for (size_t i = 0; i < _vectexs.size(); i++)
            {
                cout << "[" << i << "]" << "->" << _vectexs[i] << endl;
            }
            cout << endl;
            // 矩阵
            for (size_t i = 0; i <= _matrix.size(); ++i)
            {
                for (size_t j = 0; j <= _matrix[i].size(); j++)
                {
                    if (_matrix[i][j] == max_v)
                    {
                        cout << left << setw(6) <<  "*" << " ";
                    }
                    else
                    {
                        cout << left << setw(6) <<  _matrix[i][j] << " ";
                    }
                }
                cout << endl;
            }
        }
            
        private:
            vector<v> _vectexs; // 顶点集合
            map<v, int> _indexMap; // 顶点映射下标
            vector<vector<w>> _matrix; // 邻接矩阵
    };
    // void test1()
    // {
    //     // graph<char, int,  true> g("0123", 5);
    //     // g.addEdge('0', '1' , 1);
    //     // g.addEdge('0', '3' , 4);
    //     // g.addEdge('2', '1' , 4);
    //     // g.addEdge('1', '3' , 9);
    //     // g.addEdge('0', '1' , 8);
    //     // g.print();

        
    // }
    void test1()
    {
        // graph<
        string a[] = {"郑登亮", "刘柯汛", "刘星宇"};
        graph<string, int, true> g(a, 3);
        g.addEdge("郑登亮", "刘柯汛" ,1);
        g.addEdge("郑登亮", "刘星宇" ,2);
        g.addEdge("刘星宇", "刘柯汛" ,3);
        g.print();
    }

}

#pragma once
#include<climits>
#include<iostream>
#include<map>
#include<vector>
#include<iomanip>
#include<string>
#include<queue>
using namespace std;


namespace linkTable{
    template<class w>
    struct edges
    {
        int _disti;
        w _w;
        edges<w>* _next;
        edges(const int& dist, const w& W)
        :_disti(dist), _w(W), _next(nullptr)
        {}
    };
    template<class v, class w, bool direction = false>
    class graph{
        using edge = edges<w>;        
        public:
        // zdl:: 手动添加边
            graph(const v* a, size_t n)
            {
                _vectexs.reserve(n);
                for (int i = 0; i < n; i++)
                {
                    _vectexs.emplace_back(a[i]);
                    _indexMap[a[i]] = i;
                }
                _tables.resize(n);
            }
            size_t getVertexIndex(const v& vec)
            {
                auto it = _indexMap.find(vec);
                if (it != _indexMap.end())
                {
					return it->second;
                }
                else
                {
                    throw invalid_argument("非法的参数：顶点不存在");
                    return -1;
                }
            }
            void addEdge(const v& src, const v& dst, const w& W)
            {
                size_t srcindex = getVertexIndex(src);
                size_t disti = getVertexIndex(dst);
                edge* eg = new edge(disti, W);
                eg->_next = _tables[srcindex];
                _tables[srcindex] = eg;

                if (direction == false)
                {
                    edge* eg = new edge(srcindex, W);
                    eg->_next = _tables[disti];
                    _tables[disti] = eg;
                }
            }
            
            void print()
            {
                for (int i = 0; i < _vectexs.size(); i++)
                {
                    cout << "[" << i << "]" << "->" << _vectexs[i] << endl;
                }
                cout << endl;
                for (int j = 0; j < _tables.size(); j++)
                {
                    cout << _vectexs[j] << "[" << j << "]->" ;
                    edge* cur = _tables[j];
                    while (cur)
                    {
                        cout << _vectexs[cur->_disti] << "[" << cur->_disti << "]->" << cur->_w << " ";
                        cur = cur->_next;
                    }
                    cout << "nullptr" << endl;
                }
            }

            // zdl:: 遍历bfs
            
            
        private:
            vector<v> _vectexs; // 顶点集合
            map<v, int> _indexMap; // 顶点映射下标
            vector<edge*> _tables;//邻接表
    };
    void test1()
    {
        // graph<
        string a[] = {"郑登亮", "刘柯汛", "刘星宇"};
        graph<string, int, true>g(a , 3);
        g.addEdge("郑登亮", "刘柯汛" ,1);
        g.addEdge("郑登亮", "刘星宇" ,2);
        g.addEdge("刘星宇", "刘柯汛" ,3);
        g.print();
    }
}

//  还是需要多谢一些代码，这样代码能力才能够提升， 现在我已经有些时间没有写代码了！！
